Linear rank-width is a graph width parameter, which is a variation ofrank-width by restricting its tree to a caterpillar. As a corollary of knowntheorems, for each $k$, there is a finite obstruction set $\mathcal{O}_k$ ofgraphs such that a graph $G$ has linear rank-width at most $k$ if and only ifno vertex-minor of $G$ is isomorphic to a graph in $\mathcal{O}_k$. However, noattempts have been made to bound the number of graphs in $\mathcal{O}_k$ for$k\ge 2$. We show that for each $k$, there are at least $2^{\Omega(3^k)}$pairwise locally non-equivalent graphs in $\mathcal{O}_k$, and therefore thenumber of graphs in $\mathcal{O}_k$ is at least double exponential. To prove this theorem, it is necessary to characterize when two graphs in$\mathcal O_k$ are locally equivalent. A graph is a block graph if all of itsblocks are complete graphs. We prove that if two block graphs withoutsimplicial vertices of degree at least $2$ are locally equivalent, then theyare isomorphic. This not only is useful for our theorem but also implies atheorem of Bouchet [Transforming trees by successive local complementations, J.Graph Theory 12 (1988), no. 2, 195-207] stating that if two trees are locallyequivalent, then they are isomorphic.
展开▼
机译：线性等级宽度是图形宽度参数，它是等级宽度的变化，它通过将其树限制为毛毛虫来实现。作为已知定理的推论，对于每个$ k $，都有一个有限的障碍集$ \ mathcal {O} _k $的图，这样，当且仅当无顶点时，图$ G $的线性秩宽度最多为$ k $。 $ G $的次要元素与$ \ mathcal {O} _k $中的图同构。但是，对于$ k \ ge 2 $，没有试图限制$ \ mathcal {O} _k $中图的数量。我们表明，对于每个$ k $，在$ \ mathcal {O} _k $中至少存在$ 2 ^ {\ Omega（3 ^ k）} $ pairwise局部非等价图，因此$ \ mathcal中图的数量{O} _k $至少是双指数。为了证明该定理，有必要表征$ \ mathcal O_k $中的两个图在局部等价时。如果所有图块都是完整的图，则该图为框图。我们证明如果两个没有简单顶点至少为$ 2 $的方框图是局部等效的，则它们是同构的。这不仅对我们的定理有用，而且还暗示了Bouchet定理[通过连续的局部互补变换树，J.Graph Theory 12（1988），no。 [2，195-207]指出，如果两棵树在局部相等，则它们是同构的。
展开▼
